class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 暴力解法的思路就是固定一个起始坐标，然后向后找直到和为k，但是此时并不能停，因为数组的元素有0和负数，后面还可能存在和为k的子数组
        // 这样暴力解法的时间复杂度就为n^2
        // 优化：
        // 如果创建一个前缀和数组，dp【i】表示0~i-1的前缀和
        // 那我们就可以通过访问一遍数组下标，找以i位置为终点，0~i-1
        // 下标前缀和等于sum-k的数组个数
        // 但是想一下这样的时间复杂度，首先遍历数组构建前缀和数组，O(n)
        // ,又在遍历下标的同时循环判断0~i-1的前缀和，这样O(n^2),比暴力解法还复杂
        // 所以我们没必要遍历前缀和数组判断dp【i】是否等于sum-k
        // 只需要创建一个哈希表，映射前缀和 和 个数的映射
        // 并且我们也没必要创建一整个前缀和数组，只需要一个变量即可

        unordered_map<int,int> hash;
        hash[0]=1;
        int sum=0;
        int ret=0;
        for(auto e:nums)
        {
            sum+=e;
            if(hash.count(sum-k))
            ret+=hash[sum-k];
            hash[sum]++;
        }
        return ret;
    }
};